import com.sun.org.apache.bcel.internal.classfile.StackMapEntry;

import java.util.*;

public class Test {
}
class HashBuck2<K,V> {
    static class Node<K, V> {
        public K key;
        public V val;
        public Node<K, V> next;

        public Node(K key, V val) {
            this.key = key;
            this.val = val;
        }
    }

    public Node<K, V>[] array;
    public int usedSize;

    public HashBuck2() {
        array = (Node<K, V>[]) new Node[10];
    }

    public void put(K key, V val) {
        int hash = key.hashCode();
        int index = hash % array.length;
        Node<K, V> cur = array[index];
        while (cur != null) {
            if (cur.key.equals(key)) {
                cur.val = val;
                return;
            }
            cur = cur.next;
        }
        Node<K, V> node = new Node<>(key, val);
        node.next = array[index];
        array[index] = node;
        usedSize++;

    }
    public V get(K key){
        int hash = key.hashCode();
        int index = hash % array.length;
        Node<K,V> cur = array[index];
        while(cur != null){
            if(cur.key.equals(key)){
                return cur.val;
            }
            cur = cur.next;
        }
        return null;
    }
}
class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        //每个单词分别有几个
        Map<String,Integer> map = new HashMap<>();
        for(String x : words){
            if(!map.containsKey(x)){
                map.put(x,1);
            }else{
                int val = map.get(x);
                map.put(x,val+1);
            }
        }

        //建小根堆，得到前k个
        PriorityQueue<Map.Entry<String,Integer>> priorityQueue =
                new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
                    @Override
                    public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                        if(o1.getValue() == o2.getValue()){
                            return o1.getKey().compareTo(o2.getKey());
                        }
                        return o1.getValue().compareTo(o2.getValue());
                    }
                });
        for (Map.Entry<String,Integer> x:map.entrySet()) {
            if(priorityQueue.size() < k){
                priorityQueue.offer(x);
            }else {
                Map.Entry<String,Integer> top = priorityQueue.peek();
                if(top.getValue() == x.getValue()){
                    if(top.getKey().compareTo(x.getKey()) > 0){
                        priorityQueue.poll();
                        priorityQueue.offer(x);
                    }
                }
                if(top.getValue() < x.getValue()){
                    priorityQueue.poll();
                    priorityQueue.offer(x);
                }
            }
        }
        List<String> list = new ArrayList<>();
        for (int i=0; i<k; i++) {
            Map.Entry<String,Integer> tmp = priorityQueue.poll();
            list.add(tmp.getKey());
        }
        Collections.reverse(list);
        return list;
    }
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String s1 = in.nextLine();
            String s2 = in.nextLine();
            Find(s1, s2);
        }
    }
    private static void Find(String s1, String s2){
        Set<Character> set1 = new HashSet<>();
        for (char ch:s2.toUpperCase().toCharArray()) {
            set1.add(ch);
        }
        for(char ch:s1.toUpperCase().toCharArray()){
            if(!set1.contains(ch)){
                System.out.print(ch);
                set1.add(ch);
            }
        }
    }
    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set = new HashSet<>();
        int count = 0;
        for(int i=0; i<jewels.length(); i++){
            set.add(jewels.charAt(i));
        }
        for(int i=0; i<stones.length(); i++){
            if(set.contains(stones.charAt(i))){
                count++;
            }
        }
        return count;
    }

}
class Solution {
    //0-北边，1-西边，2-南边，3-东边
    public int robotSim(int[] commands, int[][] obstacles) {
        int direction=0;
        int max = 0;
        int[] ret = {0,0};
        for(int i=0; i<commands.length; i++){
            if(commands[i] < 0){
                direction=(direction+(commands[i]==-1?-1:1)+4)%4;
            }else{
                if(direction == 0){//北
                    for(int j=1; j<=commands[i]; j++){
                        ret[1]++;
                        if(contains(ret,obstacles)){
                            ret[1]--;
                            break;
                        }
                    }
                }else if(direction == 1){//西
                    for(int j=1; j<=commands[i]; j++){
                        ret[0]--;
                        if(contains(ret,obstacles)){
                            ret[0]++;
                            break;
                        }
                    }
                }else if(direction == 2){//南
                    for(int j=1; j<=commands[i]; j++){
                        ret[1]--;
                        if(contains(ret,obstacles)){
                            ret[1]++;
                            break;
                        }
                    }
                }else{//东
                    for(int j=1; j<=commands[i]; j++){
                        ret[0]++;
                        if(contains(ret,obstacles)){
                            ret[0]--;
                            break;
                        }
                    }
                }
            }
            max = Math.max(max,ret[0]*ret[0]+ret[1]*ret[1]);
        }
        return max;
    }
    private boolean contains(int[] ret, int[][] obstacles){
        for(int i=0; i<obstacles.length; i++){
            if(ret[0]==obstacles[i][0] && ret[1] == obstacles[i][1]){
                return true;
            }
        }
        return false;
    }
}